#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 20
#define INDENTIFY 8888
typedef struct huffman
{
    char data;
    int weight;
    int p, l, r;
    char code[MAXSIZE];
};

huffman *create_huffman(char data[], int n, int weight[])
{
    huffman *tree = (huffman *)malloc(sizeof(huffman) * (2 * n - 1));
    int visit[MAXSIZE] = {0};
    for (int i = 0; i < 2 * n - 1; i++)
    {
        if (i < n)
        {
            tree[i].data = data[i];
            tree[i].weight = weight[i];
        }
        else
        {
            tree[i].data = ' ';
            tree[i].weight = INDENTIFY;
        }
        tree[i].p = tree[i].l = tree[i].r = -1;
        // tree[i].code[0] = '\0';
    }

    for (int i = n; i < 2 * n - 1; i++)
    {
        int min_1, min_2, l, r;
        min_1 = min_2 = INDENTIFY + 1;
        l = r = -1;
        for (int j = 0; j < 2 * n - 1; j++)
        {
            if (!visit[j])
            {
                if (tree[j].weight < min_1)
                {
                    min_2 = min_1;
                    min_1 = tree[j].weight;
                    r = l;
                    l = j;
                }
                else if (tree[j].weight < min_2)
                {
                    min_2 = tree[j].weight;
                    r = j;
                }
            }
        }
        visit[l] = visit[r] = 1;
        tree[i].weight = tree[l].weight + tree[r].weight;
        tree[i].l = l;
        tree[i].r = r;
        tree[l].p = tree[r].p = i;
    }
    return tree;
}

void encode(huffman *tree, int n)
{
    char c[MAXSIZE];
    for (int i = 0; i < n; i++)
    {
        int m, p, t;
        t = i;
        m = 0;
        char ch[MAXSIZE];
        while (tree[t].p != -1)
        {
            p = tree[t].p;
            tree[p].l == t ? ch[m++] = '0' : ch[m++] = '1';
            t = p;
        }
        int k = 0;
        while (m >= 0)
        {
            tree[i].code[k++] = ch[--m];
        }
        tree[i].code[k] = '\0';
    }
}
void visit_huffuman(huffman *tree, int n)
{
    //code weight parent left right
    printf("\tcode\tweight\tparent\tleft\tright\n");
    for (int i = 0; i < 2 * n - 1; i++)
    {
        printf("%d\t%c\t%d\t%d\t%d\t%d\n", i, tree[i].data, tree[i].weight, tree[i].p, tree[i].l, tree[i].r);
    }
    for (int i = 0; i < n; i++)
    {
        printf("%s\n", tree[i].code);
    }
}
int main()
{
    /*******************code*******************/
    char *code = "abcdef";
    int weight[6] = {5, 32, 18, 7, 25, 13};
    int n = 6;
    huffman *tree = create_huffman(code, n, weight);
    // visit_huffuman(tree, n);
    encode(tree, n);
    visit_huffuman(tree, n);
    /******************************************/
    printf("\n\n****************************\n");
    printf("Press Enter key to continue\n");
    getchar();
    return 0;
    /******************************************/
}
